<?php
namespace DRY\Structure;

/**
 * DonReY Framework 2012 :: Tree-type data structure
 * Organizes data into a hierarchical model, in which each node can have "children" which are actually an ordered list.
 * Uses the "nodes store path to themselves" algorithm (relation caching) to store and access data which is efficient for both reads and writes
 *   The algorithm used only numeric node ID's in a fixed-width tables, for very fast access
 *   Provides various types of read functions (full-tree, read-children, read-descendents, path-to-node)
 *     (traversal is actually very simple with this system, even if not as fast as the preorder-traversal algorithm)
 *   Provides various write/change operations (add/remove node (with all children), cut node while keeping children, append tree to node, move node with descendants to another node)
 *     (update is efficient, only modifies nodes that are actually affected by the operation)
 *
 * @author Wavetrex <wavetrex@gmail.com>
 * @link http://www.donrey.net/Documentation/Structure/Modules/Structure/tree.html
 * @license [GPL v3] http://www.gnu.org/licenses/gpl-3.0.html
 * @version 1.0.dev
 * @package DonReY
 * @subpackage Module.Structure
 */
class Type_Tree extends base implements \Countable
{
	const FIELD_NAMES = "item_id,parent_id,position,depth,children,nodes,leaves";

	/**
	 * Primary table in the database that holds structure data (specific structures might have additional tables)
	 * @var string
	 */
	protected $_reltable;

	/**
	 * Tree specific constructor
	 * @see DRY\Structure\base::__construct()
	 */
	public function __construct(\DRY\Module\Structure $structure_module, $CFG, $id, $init_data = null, $use_observers = false)
	{
		parent::__construct($structure_module, $CFG, $id, $init_data, $use_observers);
		$this->_reltable = (string)$CFG-> storage['relations'];

		// trees do have initial data, so $init_data could contain the ID of the root node? or the request to find it at construction time
	}

	/**
	 * Prepares the proper table format for working with trees, by creating the two required tables.
	 * Also creates the necessary stored procedures, if configuration specifies that operation will use stored procedures (could be faster or slower depending on server config)
	 * @param \DRY\Module\Structure $structure_module
	 * @param \SimpleXMLElement $CFG
	 * @param bool $drop If true, it will drop any exiting tables
	 */
	public static function install_Database(\DRY\Module\Structure $structure_module, $CFG, $drop = false)
	{
		dump($CFG);
		$uses_SP = intval($CFG-> storage['storedProcedures']);

		if($uses_SP) {
			$structure_module['connection']-> query("DROP PROCEDURE IF EXISTS `Structure_Tree_Detach_remove`");
			$structure_module['connection']-> query("CREATE PROCEDURE `Structure_Tree_Detach_remove`(IN `structure` INT, IN `item` INT) MODIFIES SQL DATA
BEGIN
 CREATE TEMPORARY TABLE `__Tree_delnodes` ( `item_id` INT NOT NULL ) ENGINE=MEMORY;
 INSERT INTO `__Tree_delnodes` SELECT `node_id` AS item_id FROM `{$CFG-> storage['relations']}` WHERE `structure_id` = structure AND (`rel_id` = item OR `node_id` = item) GROUP BY `item_id`;
 DELETE FROM _struct_,_rel_ USING `__Tree_delnodes` JOIN {$CFG-> storage['table']} AS _struct_ USING (item_id) JOIN {$CFG-> storage['relations']} AS _rel_ ON `__Tree_delnodes`.item_id = _rel_.node_id WHERE _struct_.structure_id = structure AND _rel_.structure_id = structure;
 DROP TABLE `__Tree_delnodes`;
END");
		}
	}

	/**
	 * Current tree size, a cache of the count() operation
	 * @var int
	 */
	protected $totalnodes;

//===== Read Methods =====//

	/**
	 * Cached ID of the root ( is necessary for some functions )
	 * @var int
	 */
	protected $root_id = 0;

	/**
	 * Cached ID of the last read or appended node (can be used by attach_Item, append_Tree, copy_Tree etc.)
	 * @var int
	 */
	protected $last_node_id;

	/**
	 * Determines the current size of the tree ( and caches the information internally )
	 * @return int Tree size
	 */
	public function count()
	{
		if(is_null($this-> totalnodes))
			$this-> get_Root_ID();

		return $this-> totalnodes;
	}

	/**
	 * Reads the root id from the database ( minimal read )
	 * @return int
	 */
	public function get_Root_Id()
	{
		// return cached result if it exists
		if($this-> root_id)
			return $this-> root_id;

		$q = $this->_structure['queryfactory']-> select()
			-> table($this->_table, 'item_id,nodes,leaves')
			-> where("structure_id = ?", $this->_id)
			-> where("parent_id = 0")
			-> limit(1);
		$res = $this->_structure['connection']-> query($q)-> current();

		if($res) {
			$this-> last_node_id = $this-> root_id = $res['item_id'];
			$this-> totalnodes = $res['nodes'] + $res['leaves'] + 1;
			return (int)$this-> root_id;
		} else {
			// structure not found / not yet in database
			return null;
		}
	}

	/**
	 * Searches if an item is part of this tree, and grabs information related to it.
	 *   Joined mode - Prepares the query, returns the QueryFactory object
	 *   Direct mode - Returns the tree-specific information related to this item (without the item data)
	 * @param int $item_id If not specified, it searches for the Root instead
	 * @return Tree_Node|\DRY\Queryfactory\Dialect_base
	 */
	public function get_Node($item_id = null)
	{
		$this-> result_type = 'single';
		// reading query
		$q = $this->_structure['queryfactory']-> select()
			-> table(array($this->_table, "_struct_"), \DRY\Module\Queryfactory::autoalias_Add_Prefix(self::FIELD_NAMES, '_tree_'))
			-> where("_struct_.structure_id = ?", $this->_id)
			-> limit(1);
		if(is_null($item_id))
			// get root node when $item_id isn't specified.
			$q-> where("_struct_.parent_id = 0");
		else
			$q-> where("_struct_.item_id = ?", $item_id);

		if($this-> joinmode) { // joined mode
			return $q;
		} else { // actual read
			$res = $this->_structure['connection']-> query($q);
			if(!$res)
				return false; // error node not found in tree
			$res-> split_by_prefixes['__TREE'] = '_tree_';
			$node = Tree_Node::factory_Node($res);
			$this-> last_node_id = $node-> item_id;
			return $node;
		}
	}

	/**
	 * Reads the immediate children of a node and returns an array of Tree_Node objects which hold the children (without the parent node)
	 *   Joined mode - Prepares the query, returns the QueryFactory object
	 *   Direct mode - Returns the tree-specific information of the parent and it's children (wihtout the item data)
	 * This function is similar to self::get_Branch($node_id, 1), it should be a bit faster than it, however that one returns the node as well
	 * @param int $item_id Item ID or last node use of null
	 * @return bool|array[Tree_Node]|DRY_QueryFactory_Dialect Object containing the read data (first object is the specified node) or QF object
	 */
	public function get_Children($item_id=null)
	{
		if(is_null($item_id))
			$item_id = $this-> last_node_id;
		else
			$this-> last_node_id = $item_id;
		if(is_null($item_id))
			return false; // error, an item_id was not provided, and none is cached

		$this-> result_type = 'multiple';

		$q = $this->_structure['queryfactory']-> select()
			-> table(array($this->_table, "_struct_"), \DRY\Module\Queryfactory::autoalias_Add_Prefix(self::FIELD_NAMES, '_tree_')) // (#1)
			-> where("_struct_.structure_id = ?", $this->_id)
			-> where('_struct_.parent_id = ?', $item_id)
			-> order("_struct_.depth")
			-> order('_struct_.position');

		if($this-> joinmode) { // joined mode
			return $q;
		} else { // actual read
			$res = $this->_structure['connection']-> query($q);
			if(!$res)
				return false; // error, node not found in tree
			return $this-> analyse_Select_Result($res);
		}
	}

	/**
	 * Reads a segment of the tree (or the complete tree) and creates an in-memory tree containing all records
	 *   Joined mode - Prepares the query, returns the QueryFactory object
	 *   Direct mode - Returns the tree-specific information of the entire branch (wihtout the item data)
	 * @param int $item_id Node used as the root point for this branch. By default, this is null, and signifies the entire tree is read
	 *   which makes the function discover the root node and read entire tree
	 * @param int $dist_limit How deep in the tree to go ( null = no limits )
	 * @return bool|Tree_Node|\DRY\Queryfactory\Dialect_base Tree node containing the branch or QF object
	 */
	public function get_Branch($item_id=null, $dist_limit=null)
	{
		if(is_null($item_id))
			$item_id = $this-> get_Root_Id();
		$this-> last_node_id = $item_id;

		$this-> result_type = 'hierarchy';

		// setup branch-reading query
		$q = $this->_structure['queryfactory']-> select()
			-> table(array($this->_reltable, '_rel_'), false) // no fields here, just for joins
			-> where("_rel_.structure_id = ?", $this->_id)
			-> table(array($this->_table, "_struct_"), \DRY\Module\Queryfactory::autoalias_Add_Prefix(self::FIELD_NAMES, '_tree_'), 'left', "_rel_.node_id = _struct_.item_id")
			-> where("_struct_.structure_id = ?", $this->_id)
			-> where("_rel_.rel_id = ? OR _rel_.node_id = ?", $item_id, $item_id) // pick the actual link between nodes or the root point itself (necessary, because the root will generate the master container object for all the other nodes)
			-> order("_rel_.dist")
			-> order("_struct_.position");
		// add distance limit if necessary
		if(!is_null($dist_limit))
			$q-> where("_rel_.dist <= ?", $dist_limit);

		if($this-> joinmode) { // joined mode
			return $q;
		} else { // actual read
			$res = $this->_structure['connection']-> query($q);
			if(!$res)
				return false; // error, root node not found in tree
			$res-> split_by_prefixes['__TREE'] = '_tree_';
			return Tree_Node::factory_Node($res, true);
		}
	}

	/**
	 * Reads the ancestors of this node ( if they exist ) as an array of Tree_Node objects, ordered from root to itself (included)
	 *   Injector mode - Prepares the query, returns the QueryFactory object
	 *   Direct mode - Returns an array of tree-specific information of all the nodes from root to itself
	 * @param int $item_id Item ID or last node use of null
	 * @return bool|array[Tree_Node]|DRY_QueryFactory_Dialect
	 */
	public function get_Ancestors($item_id = null)
	{
		if(is_null($item_id))
			$item_id = $this-> last_node_id;
		else
			$this-> last_node_id = $item_id;
		if(is_null($item_id))
			return false; // error, an item_id was not provided, and none is cached

		$this-> result_type = 'multiple';

		$q = $this->_structure['queryfactory']-> select()
			-> table(array($this->_reltable, '_rel_'), false) // no fields here, just for joins
			-> where("_rel_.structure_id = ?", $this->_id)
			-> table(array($this->_table, "_struct_"), \DRY\Module\Queryfactory::autoalias_Add_Prefix(self::FIELD_NAMES, '_tree_'), 'left', "_rel_.rel_id = _struct_.item_id")
			-> where("_struct_.structure_id = ?", $this->_id)
			-> where("_rel_.node_id = ?", $item_id)
			-> order("_rel_.dist", 'DESC');

		if($this-> joinmode) { // joined mode
			return $q;
		} else { // actual read
			$res = $this->_structure['connection']-> query($q);
			if(!$res)
				return false; // error, node not found in tree
			return $this-> analyse_Select_Result($res);
		}
	}

	/**
	 * Searches item ID's inside the tree by a list of values of a certain database field in the data table
	 * First value must match a child of the root, the second one a distance-2 node, the third one a distance-3 node etc.
	 * If multiple solutions are found, it returns the first that matches.
	 * Does not return the "root" record, only the found ones, starting from the root's child
	 *
	 * This method is somewhat similar in concept to SimpleXMLElement's xpath() method.
	 *
	 * @param int $search_root_id The node in which the search will begin ( not included in $path_values )
	 * @param string $table_field_selector Which table field contains the values searched for
	 * @param array $path_values List of path values searched for
	 * @return bool|DRY_QueryFactory_Dialect
	 */
	public function search_Path($search_root_id, $table_field_selector, $path_values)
	{
		if(!$this-> joinmode)
			return false; // only functions in joinmode !

		$this-> last_node_id = $search_root_id;

		$this-> result_type = 'search_Path';
		$this-> search_Path = array();
		$this-> search_Path['root_id'] = $search_root_id;
		$tfs_ex = explode('.', $table_field_selector);
		$this-> search_Path['field'] = trim($tfs_ex[count($tfs_ex)>1], '`');
		$this-> search_Path['values'] = $path_values;

		return $this->_structure['queryfactory']-> select()
			-> table(array($this->_reltable, '_rel_'), false) // no fields here, just for joins
			-> where("_rel_.structure_id = ?", $this->_id)
			-> table(array($this->_table, "_struct_"), \DRY\Module\Queryfactory::autoalias_Add_Prefix(self::FIELD_NAMES, '_tree_'), 'left', "_rel_.node_id = _struct_.item_id")
			-> where("_struct_.structure_id = ?", $this->_id)
			-> where("_rel_.rel_id = ?", $search_root_id) // similar with read branch, however because of filtering condition...
			-> where("_rel_.dist <= ?", count($path_values))
			-> where("$table_field_selector IN (?)", $path_values) // ...only nodes that have a specific values are picked, and they must be in the proper order
			-> order("_struct_.depth");
	}

	/**
	 * Indicates the type of result expected when running in injection mode, so analyse_Select_Result() knows if the result is one node, multiple independent nodes or a branch of linked nodes
	 * @var string
	 */
	private $result_type;

	/**
	 * Takes the parts from a select query result which are relevant to the tree organization and constructs a Tree_Node out of it. Used in Joined mode
	 * @param \DRY\Database\Driver_result_base $res The result object
	 * @return Tree_Node|array[Tree_Node]
	 */
	public function &analyse_Select_Result(\DRY\Database\Driver_result_base $res)
	{
		$res-> split_by_prefixes['__TREE'] = '_tree_';
		switch($this-> result_type) {

			// only one entry
			case 'single':
				$r = Tree_Node::factory_Node($res);
				break;

			// tree branch in pre-order (parent, child, child)
			case 'hierarchy':
				$r = Tree_Node::factory_Node($res, true);
				break;

			// individual rows which do not necesarely have a parent-child relationship (might be siblings, or a chain of ancestors, or any other linear result)
			case 'multiple':
				$r = array();
				foreach($res as $row)
					$r[$row['__TREE']['item_id']] = Tree_Node::factory_Node($res, false);
				break;

			// special mode in which results are picked depending on some conditions
			case 'search_Path':
				$check_node = $this-> search_Path['root_id'];
				$current_search = 0;
				$minimum_depth = 0;

				$r=array(); // contains references to tree_entry objects, key is record_id
				foreach($res as $row) {
					$id = $row['__TREE']['item_id'];
					if($row['__TREE']['depth'] > $minimum_depth && $row[$this-> search_Path['field']]==$this-> search_Path['values'][$current_search] && $row['__TREE']['parent_id']==$check_node) {
						$check_node = $id; // $path_values[$current_search]
						$r[$id] = Tree_Node::factory_Node($res, false);

						// continues path search
						$minimum_depth = $row['__TREE']['depth'];
						$current_search++;
					}
				}
				unset($this-> search_Path);
				break;
		}
		return $r;
	}

//===== Change/Write Methods =====//

	/**
	 * Sets which item ID to be the root of this tree
	 *
	 * @param int $item_id The ID of the item which becomes root
	 */
	public function create_Root($item_id)
	{
		if($this-> root_id)
			return false; // root_id is set, so there is already a root in this tree

		$this-> root_id = $item_id;
		$this-> last_node_id = $item_id;

		// check if an item is already part of this tree (read the entry), to avoid corrupting the trees table
		$q = $this->_structure['queryfactory']-> select()
			-> table($this->_table, 'item_id')
			-> where("structure_id = ?", $this->_id)
			-> where("item_id = ?", $item_id)
			-> limit(1);
		if($this->_structure['connection']-> query($q)-> current())
			return false; // error, entry found, the node is already part of the tree (maybe even the root)

		// insert the root into primary table
		$this->_structure['connection']-> query(
			$this->_structure['queryfactory']-> insert()
			-> table($this->_table)
			-> values(array(
				'structure_id'=> $this->_id,
				'item_id'=> $item_id,
				'parent_id'=> 0
			))
		);

		// insert into relations table the self-link (which represents the root) - It's necessary for the more complex tree operations, which have the relations table as primary table
		$this->_structure['connection']-> query(
			$this->_structure['queryfactory']-> insert()
				-> table($this->_reltable)
				-> values(array(
					'structure_id'=> $this->_id,
					'node_id'=> $item_id,
					'rel_id'=> 0,
					'dist'=> 0
				))
		);
	}

	/**
	 * Attaches an item to this tree, using $link_to as the attach point ( as the new node's parent )
	 *
	 * @param int $item_id New item ID
	 * @param int $link_to Parent item ID - If null, it uses the last node that was read or specified in this method
	 * @param string|int $position In what position inside parent node to attach. Possible values: 'last', 'first', {positive number} - any number > children count = Append as last children, 0 = 'first'
	 * @return int Position of the new created node
	 */
	public function attach_Item($item_id, $link_to = null, $position = 'last')
	{
		if(is_null($link_to))
			$link_to = $this-> last_node_id;
		else
			$this-> last_node_id = $link_to;
		if(is_null($link_to))
			return false; // error, an value for link_to was not provided, and none is cached

		$qf = $this->_structure['queryfactory'];
		$db = $this->_structure['connection'];

		// checks if the item is not already part of this tree (fast read)
		$q = $qf-> select()
			-> table($this->_table, 'item_id')
			-> where("structure_id = ?", $this->_id)
			-> where("item_id = ?", $item_id)
			-> limit(1);
		if($db-> query($q)-> current())
			return false; // error, entry found, the node is already part of the tree (maybe even the root)

		// reads the parent's tree data (while also checking if it exists and is part of the tree)
		$q = $qf-> select()
			-> table($this->_table, 'depth,children,nodes,leaves')
			-> where("structure_id = ?", $this->_id)
			-> where("item_id = ?", $link_to)
			-> limit(1);

		$parent_entry = $db-> query($q)-> current();
		if(!$parent_entry)
			return false; // error, parent not found

		// copy relations from the parent node to this new one, if not root (as root doesn't have any relations to copy from) - INSERT ... SELECT
		if($parent_entry['depth'] > 0) {
			$q = $qf-> insert()
				-> table($this->_reltable)
				-> values($this->_structure['queryfactory']-> select()
					-> table($this->_reltable, array('structure_id', 'node_id'=> $item_id, 'rel_id', 'dist'=>"(`dist` + 1)"))
					-> where('structure_id = ?', $this->_id)
					-> where('node_id = ?', $link_to)
				);
			$db-> query($q);
		}
		// safeguard against multithreding, because this function runs multiple queries to construct the proper data
		$db-> query('LOCK TABLES '.$this->_table.' WRITE, '.$this->_reltable.' WRITE');

		// creates the entry in primary table; Position is autogenerated by the auto-increment system
		if($position == 'first')
			$position = 0; // insert before first element, which should have 'position' = 1

		if(is_int($position) && $position < $parent_entry['children']) {
			// increase postion for all siblings with 'position' > $position
			$q = $qf-> update()
				-> table($this->_table)
				-> where("structure_id = ?", $this->_id)
				-> where("parent_id = ?", $parent_entry['item_id'])
				-> values(array("position"=>"position + 1"), null, true)
				-> order('position', "DESC")
				-> where('position > ?', $position);
			$db-> query($q);
			$position++;
		} else
			$position = $parent_entry['children'] + 1;

		// insert the new node in the primary table
		$q = $qf-> insert()
			-> table($this->_table)
			-> values(array(
				'structure_id'=> $this->_id,
				'item_id'=> $item_id,
				'parent_id'=> $link_to,
				'depth'=> $parent_entry['depth']+1,
				'position'=> $position
			));
		$db-> query($q);

		// creates the direct parent-child link into relations table
		$q = $qf-> insert()
			-> table($this->_reltable)
			-> values(array(
				'structure_id'=> $this->_id,
				'node_id'=> $item_id,
				'rel_id'=> $link_to
			));
		$db-> query($q);

		// updates the parent ( number of children + 1, number of leaves + 1 )
		$q = $qf-> update()
			-> table($this->_table)
			-> values(array(
				'children'=> $parent_entry['children']+1,
				'leaves'=> $parent_entry['leaves']+1
			))
			-> where("structure_id = ?", $this->_id)
			-> where("item_id = ?", $link_to);
		$db-> query($q);

		// updates all the parent's ancestors ( number of leaves + 1 if parent was already a node OR number of nodes + 1 if parent was a leaf )
		if($parent_entry['depth']>0) { // only if parent wasn't root )
			$q = $qf-> update()
				-> table($this->_reltable, false)
				-> table($this->_table, null, "left", "#1.rel_id = #2.item_id")
				-> where("#1.structure_id = ?", $this->_id)
				-> where("#2.structure_id = ?", $this->_id)
				-> where("#1.node_id = ?", $item_id)
				-> where("#1.dist > 1");

			if($parent_entry['children'] > 0)
				$q-> values(array('leaves'=>'leaves + 1'), $this->_table, true);
			else
				$q-> values(array('nodes'=>'nodes + 1'), $this->_table, true);
			$db-> query($q);
		}

		$db-> query("UNLOCK TABLES");
		return $position; // done, attached
	}

	/**
	 * Detaches an item from the tree.
	 * There are two ways of detaching:
	 * - With all it's branch (default) ($child_mode: "remove")
	 * - Only itself, while connecting all it's children to the parent node ($child_mode: "linkup")
	 * NOTE: The root of the tree cannot be detached. Use Data_Structure_Tree::destroy() function to remove the root (along with all the entries)
	 *
	 * @param int $item_id
	 * @param string $child_mode
	 */
	public function detach_Item($item_id, $child_mode = 'remove')
	{
		$qf = $this->_structure['queryfactory'];
		$db = $this->_structure['connection'];

		// checks if the item is really part of this tree (read it)
		$q = $qf-> select()
			->table($this->_table, self::FIELD_NAMES)
			->where("structure_id = ?", $this->_id)
			->where("item_id = ?", $item_id)
			->limit(1);
		$tree_entry = $db-> query($q)-> current();
		if(!$tree_entry)
			return false; // error, entry not found

		if($tree_entry['parent_id'] == 0)
			return false; // error, cannot detach Root node

		// reads the parent's information (the parent will get updated)
		$q = $qf-> select()
			->table($this->_table, 'children,nodes,leaves')
			->where("structure_id = ?", $this->_id)
			->where("item_id = ?", $tree_entry['parent_id'])
			->limit(1);

		$parent_entry = $db-> query($q)-> current();

		// safeguard against multithreding, because this function runs multiple queries to construct the proper data
		$db-> query('LOCK TABLES '.$this->_table.' WRITE, '.$this->_reltable.' WRITE');

		if($child_mode=='remove') { // remove the node and all it's children
			// $tree_entry[ nodes, leaves ] will contain the number of nodes and leaves that will be removed from all ancestors
			if($tree_entry['children']==0)
				$tree_entry['leaves']++; // record node was leaf, no children
			else
				$tree_entry['nodes']++;

			// recalculate parent_entry nodes & leaves
			$parent_entry['nodes']-= $tree_entry['nodes'];
			$parent_entry['leaves']-= $tree_entry['leaves'];
			$parent_entry['children']--;

			// it was only child, parent was converted to leaf ( N-1, L+1 ) - This modifies the values for ancestors
			if($parent_entry['children']==0) {
				$tree_entry['nodes']++;
				$tree_entry['leaves']--;
			}

			// All this updating/deleting could be done using a stored procedure? - It would simplify the code here, and also make it slightly quicker (perhaps)

			// update the parent node with new number of children, nodes, leaves
			$q = $qf-> update()
				-> table($this->_table)
				-> where("structure_id = ?", $this->_id)
				-> where("item_id = ?", $tree_entry['parent_id'])
				-> values($parent_entry);
			$db-> query($q);

			// updates all the parent's ancestors to new number of nodes/leaves (if the parent wasn't the root)
			if($tree_entry['depth']>1) {
				$q = $qf-> update()
					-> table($this->_reltable, false)
					-> where("#1.structure_id = ?", $this->_id)
					-> table($this->_table, null, "left", "#1.rel_id = #2.item_id")
					-> where("#2.structure_id = ?", $this->_id)
					-> where("#1.node_id = ?", $item_id)
					-> where("#1.dist > 1")
					-> values(array(
						'nodes'=> "nodes - {$tree_entry['nodes']}",
						'leaves'=> "leaves - {$tree_entry['leaves']}"
					), $this->_table, true);
				$db-> query($q);
			}

			// delete node entries from the two tables, the detached node and all it's children. Done in one shot, using a joined-delete with a temporary table which contains a list of all nodes to be deleted
			$db-> query($qf-> create("table")
				-> flags("temporary", "MEMORY")
				-> name("__Tree_delnodes")
				-> column("item_id", "int")
			);

			// fill the temp table with INSERT ... SELECT
			$db-> query($qf-> insert()
				-> table('__Tree_delnodes')
				-> values($qf-> select()
					-> table($this->_reltable, 'node_id:item_id')
					-> where("structure_id = ?", $this->_id)
					-> where("rel_id = ? OR node_id = ?", $item_id, $item_id) // either children or the node itself
					-> group("item_id")
				)
			);

			// remove itself and all children from both tables (using the list of nodes that was created in the previous query)
			$db-> query($qf-> delete()
				-> table("__Tree_delnodes", null, null, null, true) // no delete, will get dropped next
				-> table($this->_table, null, "join", "(item_id)")
				-> where("#2.structure_id = ?", $this->_id)
				-> table($this->_reltable, null, "join", "#1.item_id = #3.node_id")
				-> where("#3.structure_id = ?", $this->_id)
			);

			$db-> query($qf-> drop('table')
				-> name("__Tree_delnodes")
			);

			// now, since the node has dissapeared, update it's siblings positions (if they exist, and the node wasn't in the last position)
			if($parent_entry['children']>0 && $tree_entry['position']<=$parent_entry['children']) {
				$db-> query($qf-> update()
					-> table($this->_table)
					-> values(array('position'=>"`position` - 1"), null, true)
					-> where("structure_id = ?", $this->_id)
					-> where("parent_id = ?", $tree_entry['parent_id'])
					-> where("position > ?", $tree_entry['position'])
					-> order("position", "ASC")
				);
			}

		} else { // TODO: remove only the node, and link it's children to the parent ( "linkup" )

			// 1. Update parent - number of children changes (node.children - 1)

			// 2. Update parent AND ancestors - number of nodes or leaves decreases by 1

			// 3. Remove the node entry in (_table) to clear the way for new sibling positions

			// 4. Update siblings position (node.children-1) - Children are inserted in the position where the node was

			// 5. Update first tier children of the node, set the parent to be the parent of the detached node, set positions to be proper positions under new parent

			// 6. Update all descendants, decrease depth by 1

			// 7. Get the list of ancestors this node has (necessary for updating relations) (_reltable)

			// 8. Get the list of descendants this node has (necessary for updating relations) (_reltable)

			// 9. Delete all relations between the detached node and other nodes (where node_id = (id) or rel_id = (id))

			// 10. Decrease dist for all descendants (node_id IN ($desc)) which had any of the ancestors (rel_id IN ($anc)) by 1

			// not necesary in this exact order...
		}

		$db-> query("UNLOCK TABLES");
		return true; // done, attached
	}

	/**
	 * Copies a node and all it's children into a new tree structure, or an existing one by appending all the nodes from this tree
	 * @param int $node_id
	 * @param int $structure_id
	 * @param int $destination_node_id If not null, it's a copy-append operation, instead of creating a blank tree
	 */
	public function copy_Tree($node_id, $structure_id, $destination_node_id = null)
	{

	}

	/**
	 * Extracts a node with all children from this tree and creates another tree structure in which the $node_id will be root
	 *   Note: This is faster than copying and deleting, because it only updates records with new information, doesn't insert and remove.
	 * @param int $node_id
	 * @param int $new_structure_id
	 * @param int $keep_node Makes a copy of the node to the new tree, keeping it in the original tree. The children however are moved
	 *   This is useful to facilitate reattachment using append_Tree(), with $skip_root = true
	 */
	public function split_Tree($node_id, $structure_id, $keep_node = false)
	{

	}

	/**
	 * Combines another tree with this one by connecting the second tree's nodes to the specified $node_id. This is the reverse operation of split_Tree()
	 * @param int $item_id
	 * @param int $structure_id
	 * @param bool $skip_root If False, the root is appended to the node. If True, the root is disgarded and all it's children are appended to the node instead.
	 */
	public function append_Tree($item_id, $structure_id, $skip_root = false)
	{

	}

	/**
	 * Removes the entire tree
	 * @see DRY\Structure\base::destroy()
	 */
	public function destroy()
	{
		// TODO: Support joined mode deletion ( so it deletes the data too if necessary )

		// delete the relations table
		$q = $this->_structure['queryfactory']-> delete()
			->table($this->_reltable)
			->where("structure_id = ?", $this->_id);
		$this->_structure['connection']-> query($q);

		// delete the master table
		$q = $this->_structure['queryfactory']-> delete()
			->table($this->_table)
			->where("structure_id = ?", $this->_id);
		$this->_structure['connection']-> query($q);

		$this-> totalnodes = 0;
		$this-> root_id = null;
		return $this->_structure['connection']-> affected_rows;
	}

}

/**
 * Memory representation of a tree node, also contains the data that was read when using query injection
 * For all changing operations, tables are locked during updates to prevent corruption of the database due to multithreading
 *
 * Has suplimentary methods for processing tree entries (navigation of children, etc.)
 *
 * @author Wavetrex <wavetrex@gmail.com>
 * @link http://www.donrey.net/Documentation/Structure/Modules/Structure/tree.html
 * @license [GPL v3] http://www.gnu.org/licenses/gpl-3.0.html
 * @version 1.0.dev
 * @package DonReY
 * @subpackage Module.Structure
 */
class Tree_Node implements \Countable, \IteratorAggregate
{

	/**
	 * Extra fields when the tree entry was read with the data (in joined mode)
	 *
	 * @var array
	 */
	public $data;

	/**
	 * ID of this node
	 * @var int
	 */
	public $item_id;

	/**
	 * ID if the node which is parent to this one
	 *
	 * @var int
	 */
	public $parent_id;

	/**
	 * How deep the entry is in the tree. Root has 0, it's children 1, etc.
	 *
	 * @var int
	 */
	public $depth;

	/**
	 * Position related to it's siblings. First child = 1, last child = number of children of the parent
	 *
	 * @var int
	 */
	public $position;

	/**
	 * Statistical data (stored in the primary table) - Array having 3 values:
	 * [c] - Number of children (direct descendants) of this entry
	 * [n] - Number of subnodes (descendants that also have children)
	 * [l] - Number of leaves (descendants which do not have children of their own)
	 * @var array[3]
	 */
	public $stats;

	/**
	 * Array of objects of this class, each containing a child of the current entry, ordered; Key is item_id
	 * If empty, this node does not have children
	 *
	 * @var array[Tree_Node]
	 */
	public $children = array();

	/**
	 * Transforms a database result object into a Tree_Node, by analysing all rows and the relations between them
	 * @param \DRY\Database\Driver_result_base $res Database result object
	 * @param bool $hierarchy If False, it expects only one result row. If True, it expects the result to contain a tree branch, with first node being the branch's root
	 */
	public static function &factory_Node(\DRY\Database\Driver_result_base $res, $hierarchy = false)
	{
		if($hierarchy) {
			// Construct the in-memory tree out of the database result
			$locations=array(); // contains references to \DRY\Structure\Tree_Node objects, key is item_id
			$root_id = null;
			foreach($res as $row) {
				// first node in the reslt is the root
				if(is_null($root_id))
					$root_id = $row['__TREE']['item_id'];
				// fill $locations with Tree_Node objects
				$node_id = $row['__TREE']['item_id'];
				$locations[$node_id] = new self($row);
				// construct in-memory tree using references
				if($node_id!=$root_id)
					$locations[$row['__TREE']['parent_id']]-> children[$node_id] = &$locations[$node_id];
			}
			return $locations[$root_id];
		} else {
			// Just one node, no children
			$node = new self($res-> current());
			return $node;
		}
	}

	/**
	 * Constructs this object
	 * @param array $row Row of a result from a query
	 */
	protected function __construct($row)
	{
		$this-> item_id = (int)$row['__TREE']['item_id']; // actual item this tree node refers to
		$this-> parent_id = (int)$row['__TREE']['parent_id']; // id of the parent item in relation to this node
		$this-> position = (int)$row['__TREE']['position']; // position of this tree node in relation to it's siblings
		$this-> depth = (int)$row['__TREE']['depth']; // distance to the root node of the tree from this node
		$this-> stats = array(
			'c'=> (int)$row['__TREE']['children'],
			'n'=> (int)$row['__TREE']['nodes'],
			'l'=> (int)$row['__TREE']['leaves']
		);
		// any other fields which do not belong to the Tree structure become part of the Data
		unset($row['__TREE']);
		$this-> data = (array)$row;
	}

	/**
	 * Transforms this hierarchical object into an array of \DRY\Structure\Tree_Node objects which are sorted in preorder mode.
	 * @param array $array Can be used with existing array or it creates a fresh one
	 */
	public function &traverse_Preorder(&$array = null)
	{
		if(is_null($array))
			$array = array();

		$array[$this-> item_id] = clone($this);
		unset($array[$this-> item_id]-> children); // no longer needing children, since the tree becomes linear
		foreach($this-> children as $child)
			$child-> traverse_Preorder($array);

		return $array;
	}

	/**
	 * Transforms this hierarchical object into an array of \DRY\Structure\Tree_Node objects which are sorted in postorder mode
	 * @param array $array Can be used with existing array or it creates a fresh one
	 */
	public function &traverse_Postorder(&$array = null)
	{
		if(is_null($array))
			$array = array();

		foreach($this-> children as $child)
			$child-> traverse_Postorder($array);

		$array[$this-> item_id] = clone($this);
		unset($array[$this-> item_id]-> children); // no longer needing children, since the tree becomes linear

		return $array;
	}

	/**
	 * Returns number of in-memory children this node has (not the actual number of children of the tree node) - Countable implementation
	 *
	 * @return int Number of children
	 */
	public function count()
	{
		return count($this-> children);
	}

	/**
	 * Allows using foreach() on this element to enumerate all child elements - IteratorAggregate implementation
	 *
	 * @return ArrayIterator
	 */
	public function getIterator()
	{
		return new \ArrayIterator($this-> children);
	}

}
